package leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
/**
 * 1.  这个题 可以 用 滑动 窗口 来写  超时   掌握 运用 滑动窗口 求解 区间 最值的 方法
 * 2.  单调栈 的 使用 使 该题 直接 时间复杂度 非常的底  单调栈的 使用
 * 3. 不要什么 时候 就想着 直接用 递归回溯 来解决  问题 思考一下 for循环
 * 以及嵌套for循环能不能解决        （这就要求 你要 十分 理解这 两者的  区别） 
 * 
 * 4.借该题 直接  去真正的  去了解一下   嵌套 for循环和 递归 嵌套 for 的区别 
 * 这直接  能明白很多东西
 *    
 *   别忘了 递归  就是   循环的 对吧    只不过   循环的   逻辑   是一样的 
 * @author I adore you
 *
 */
public class leetocde2104子数组范围求和final {
	public static int maxAndMinSubValue(int start,int end,int nums[]) {
		Deque<Integer> max = new ArrayDeque<>(); 
		Deque<Integer> min =new ArrayDeque<>();
		for(int i = start; i <= end;i++) {
			while(!max.isEmpty() && nums[max.peekLast()] <= nums[i]) {
				max.removeLast();
			}
			// 添加的是索引   这样的好处 不言而喻 对吧 很多 方便之处  
			max.addLast(i);
			while(!min.isEmpty() && nums[min.peekLast()]>=nums[i]) {
				min.removeLast();
			}
			min.addLast(i);
		}
		
//		return Arrays.asList(max.peekFirst(),min.peekFirst());
		return nums[max.peekFirst()] - nums[min.peekFirst()];
	}
	// ② for 循环  结合 滑动窗口    TLE 了
	public static int solution(int nums[]) {
		int sum=0;	
		for(int i = 0; i < nums.length-1;i++) {
				for(int j = i+1; j < nums.length;j++) {
					sum+=maxAndMinSubValue(i,j,nums);
				}
			}
		
		return sum;
	}
	/**
	 * ① 对于这道题 来说 这是错的    数组的长度 越大   操作的 重复的子区间 就越多 
	 * 花时间 整明白  递归回溯 和 嵌套 for 的区别 
	 * 暴力 是解决 问题的 一个 直接显示的 方法 对吧 优化  应该是 从暴力的角度去思考为啥 会 慢
	 * 捕蝇叮咬非要 用递归  来实现暴力  可以用我们最擅长的 嵌套 for 循环啊 这不是 更容易去想
	 * 这个 题用 嵌套for 循环的 话 就不会 浪费 很多的  时间来构建 这个递归怎么写
	 * @param index
	 * @param nums
	 * @param len
	 * @return
	 */
	public static int process(int index,int nums[],int len) {
		// 等一下看看 这能不能 直接 删除
		if(index == len-1) {
			return 0;
		}
		int sum=0;
		for(int i = index;i < len-1;i++) {
			System.out.println(index+" "+(i+1));
			//  这他妈 吃了 已经 不只 一次的亏了沙雕      还传参数index+1
			/**
			 *  这还是有重复的 索引过程   
			 *  怎么在回溯 消除 这个重复 这是个问题
			 *  但是 可以在 maxAndMinSubValue 中建立个 索引二维表 来消除 但这样时间 空间复杂度都会 增加  
			 */
			sum+=maxAndMinSubValue(index,i+1,nums)+process(i+1,nums,len);
		}
		return sum;
	}
	
	/**
	 * ③
	 * 其实这里 用for 循环的时候 忽略 了 一个  重要的  问题  在枚举 子区间的 过程中 
	 * 顺便 可以 把 该区间的最值 求出来的  这样 不 就 快了
	 * 
	 */
	public static long solution(int nums[],int len) {
			//嵌套for 循环 是枚举 子连续 的区间 在枚举的过程中 直接 把最值  也给 算出来 就是这样的一个过程
		long sum=0L;	
		for(int i = 0;i < len-1; i++) {
				int max = nums[i];
				int min = nums[i];
				for(int j = i+1;j < len;j++) {
					if(nums[j] > max) {
						max=nums[j];
					}
					min = nums[j] < min ?nums[j]:min;
					sum+=max-min;
				}
			} 
		return sum;
	}
	
	public static void main(String args[]) {
//		int nums[] = {3,2,1};
		int []nums = {4,-2,-3,4,1};
//		int ans=process(0,nums,nums.length);
		long ans = solution(nums,nums.length);
		System.out.println(ans);
	}
}